package com.hqq.exercise.array;

/**
 * FindGreatestSubArray 连续子数组的最大和
 * 题目描述:
 * 输入一个整型数组，数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)。
 * 样例输入:
 * {1,-2,3,10,-4,7,2,-5}
 * 样例输出:
 * {3,10,-4,7,2}
 * Created by heqianqian on 2017/8/18.
 */
public class FindGreatestSubArray {

    public static void main(String[] args) {
        System.out.println(findGreatestSubArray(new int[]{0,0,0,0,0}));
        //System.out.println(findGreatestSubArray(new int[]{1, -1, -1, -1}));
        //System.out.println(findGreatestSubArray(new int[]{-23, 17, -7, 11, -2, 1, -34}));
    }

    public static int findGreatestSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return -65535;
        }
        int currentSum = array[0], maxSum = array[0];//当前计算总和和最大总和
        for (int i = 1; i < array.length; i++) {
            currentSum += array[i];
            maxSum = Math.max(maxSum, currentSum);
            if (array[i] > maxSum) {//如果当前值之前元素累加的和都要大
                currentSum = array[i];
                maxSum = array[i];
            }
        }
        return maxSum;
    }
}
